package aufgabe4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Pattern;

public class EnhancedSuffixArray {
	public final String s;
	public final String[] SSUF;
	public final int[] SUF;
	private final int[] SUFINVERS;
	public int[] LCP;
	private final int slength;

	public EnhancedSuffixArray(String string) {
		s         = string;
		slength   = string.length();
		SSUF      = new String[slength];		
		SUFINVERS = new int[slength];
		SUF       = new int[slength];
		LCP       = new int[slength];
        
        for (int i = 0; i < slength; i++) SSUF[i] = string.substring(i);
        	
        Arrays.sort(SSUF);
        
        for (int i = 0; i < slength; i++) {
        	SUF[i]            = slength - SSUF[i].length();
        	SUFINVERS[SUF[i]] = i;
        }        
        
        calcLcpTable(string);
	}
	
	protected void calcLcpTable(String s) {
		int l = 0;
		
		for (int i = 0; i < slength; i++) {
			int j = SUFINVERS[i];
			
			if (j > 0) {
				int k = SUF[j-1];
				l     = Math.max(l-1, 0);
				
				if (!(k+l >= slength) || (i+l >= slength)) {
					while (s.charAt(k+l) == s.charAt(i+l)) {
						l++;
						
						if ((k+l >= slength) || (i+l >= slength)) break;
					}
				}				
				
				LCP[j] = l;
			}
		}
	}
	
	protected List<Integer> getLocalMaxima(int l) {
		List<Integer> result = new ArrayList<Integer>();
		
		for (int i = 1; i < slength-1; i++) {			
			if (LCP[i] > LCP[i-1] && LCP[i] > LCP[i+1] && LCP[i] >= l) {
				result.add(i);
			}
			
			if (i == slength-2 && LCP[i+1] > LCP[i] && LCP[i] >= l) {
				result.add(i+1);
			}
		}
		
		return result;
	}
	
	public void getMaximalUniqueMatches(int l) throws Exception {
		int p = s.indexOf('#');
		
		if (p == -1) {
			throw new Exception("The delimiter # is missing.");
		}
		
		for (int j: getLocalMaxima(l)) {
			int i = j-1;
			int lcpLength = LCP[j];
			
			// check if i+1=j is not necessary, because i=j-1
			
			if (SUF[i] > SUF[j]) {
				int temp = i;
				i        = j;
				j        = temp;
			}
			
			if (SUF[i] == 0 || s.charAt(SUF[i]-1) != s.charAt(SUF[j]-1) && SUF[i] < p && p < SUF[j]) {
				System.out.println(""+SUF[i]+"\t"+SUF[j]+"\t"+lcpLength+"\t"+s.substring(SUF[i], SUF[i]+lcpLength));
			}
		}
	}
	
	public void printTables() {
		System.out.println("i\tSUF\tLCP\tSUF-1\tSSUF");
		for (int i = 0; i < SUF.length; i++) System.out.println(i+"\t"+SUF[i]+"\t"+((i==0)?"-":LCP[i])+"\t"+SUFINVERS[i]+"\t"+SSUF[i]);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {		
		@SuppressWarnings("resource")
		Scanner scanner = new Scanner(new java.io.BufferedInputStream(System.in), "UTF-8");
		
		if (!scanner.hasNextLine()) {
			System.out.println("No input given.");
			System.exit(1);
		}
		
		String s = scanner.useDelimiter(Pattern.compile("\\A")).next().replaceAll("\n", " ").trim();
		
		System.out.println("Input String: "+s+"\n");
		
		(new EnhancedSuffixArray(s)).printTables();
	}
}
